package com.ting.test.algorithms.二叉树;

/**
 * 搜索二叉树概念:
 * 1. 二叉树的每一个子树都是搜索二叉树
 * 2. 左子树的最大值小于根节点
 * 3. 右子树最小值大于根节点
 * 子树的概念：
 * 1.一棵树的叶子节点是一个子树
 * 2.他本身也是一个子树
 * 3. 子树必须包含头结点以下所有节点，不能随机挑
 * 利用递归的思想
 * 1.
 */
public class 判断最大子树是搜索二叉树 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        Info info = process(generateRandomBST(4,5));
        System.out.println(info.maxSubBSTTreeSize);
    }

    private static Info process(TreeNode node) {
        //base case
        if (null == node) {
            return null;//空节点不好返回 直接给空
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);


        int allSize;//当前树的大小
        int min = node.val;
        int max = node.val;

        if (leftInfo != null) {
            //当前树的最大值最小值，是从左右树中与当前val比较而来
            min = Math.min(leftInfo.min, node.val);
            max = Math.min(leftInfo.max, node.val);
        }


        if (rightInfo != null) {
            //当前树的最大值最小值，是从左右树中与当前val比较而来
            min = Math.min(rightInfo.min, node.val);
            max = Math.min(rightInfo.max, node.val);
        }
        // 当前树的大小就是左右树+1
        int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
        int rightSize = rightInfo == null ? 0 : rightInfo.allSize;

        allSize = leftSize + rightSize + 1;
        //判断当前数的最大搜索二插子树有两种情况
        //1. 当前节点包含在内
        //要判断当前节点所在的整棵树是否是搜索二叉树
        int p1 = -1;
        //如果左子树为空，则左子树是BST，或者如果左子树的最大搜索二叉树大小是他本身的大小，说明左子树是搜索二叉树
        boolean leftBST = leftInfo == null ? true : leftInfo.maxSubBSTTreeSize == leftInfo.allSize;
        // 右子树也是一样
        boolean rightBST = rightInfo == null ? true : rightInfo.maxSubBSTTreeSize == rightInfo.allSize;

        // 判断是否搜索二叉树的条件是 左右子树都是BST 且左子树最大值小于val,右子树最小值大于val
        if (leftBST && rightBST && (leftInfo.max < node.val && rightInfo.min > node.val)) {
            p1 = leftInfo.allSize + rightInfo.allSize + 1;
        }


        //2.当前节点不包含在内，
        // 最大搜索二叉树子树要么是左子树，要么是右子树
        int p2 = -1;
        int leftMaxSUbBSTSize = leftInfo == null ? 0 : leftInfo.maxSubBSTTreeSize;
        int rightMaxSUbBSTSize = rightInfo == null ? 0 : rightInfo.maxSubBSTTreeSize;
        p2 = leftMaxSUbBSTSize < rightMaxSUbBSTSize ? rightMaxSUbBSTSize : leftMaxSUbBSTSize;

        return new Info(allSize, Math.max(p1, p2), min, max);

    }


    static class Info {
        int allSize;//当前树的大小
        int maxSubBSTTreeSize;//当前树的最大搜索二叉树子树的大小
        int min;
        int max;

        public Info(int allSize, int maxSubBSTTreeSize, int min, int max) {
            this.allSize = allSize;
            this.maxSubBSTTreeSize = maxSubBSTTreeSize;
            this.min = min;
            this.max = max;
        }
    }



    // for test
    public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static TreeNode generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        TreeNode head = new TreeNode((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

}
